﻿/// <summary>
/// https://leetcode-cn.com/problems/longest-valid-parentheses/
/// </summary>
public class Solution
{
    private IEnumerable<int> GetDifferences(IEnumerable<int> items, int? firstValue = null)
    {
        var current = firstValue ?? items.FirstOrDefault();
        foreach (var item in items)
        {
            yield return (item - current);
            current = item;
        }
    }
    public int LongestValidParentheses(string s)
    {
        Stack<int> leftBrackets = new Stack<int>();
        List<int> badBrackets = new List<int>
        {
            s.Length
        };

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
                leftBrackets.Push(i);
            else if (!leftBrackets.TryPop(out _)) // if(s[i] == ')')
                badBrackets.Add(i);
        }

        badBrackets.AddRange(leftBrackets);

        badBrackets.Sort();
        return this.GetDifferences(badBrackets, -1).Max() - 1;
    }
}